package hot100;


/*
 * Author：江松
 * Date：2023/4/7 11:19
 *
 *
 完全平方数:
 1,贪心策略失败了，贪心：12=9+1+1+1，结果是12=4+4+4
 2,动态规划
 fi表示数i最小平方数组成的个数，
 并且初始化i：如果为平方数fi=1，反之fi=i
 划分为k属于1~i-1，则有fi=min(f[k]+f[i-l])
 */

public class Main279 {

    public int numSquares(int n) {
        int f[]=new int[n+1];
        f[1]=1;
        int base=1;
        for(int i=1;i<=n;++i){
            int pow=(base+1)*(base+1);
            if(i==pow){
                f[i]=1;
                base+=1;
            }else{
                f[i]=i;
            }
            for(int j=1;j<=i/2;++j){
                f[i]=Math.min(f[i],f[i-j]+f[j]);
            }
        }
        return f[n];
    }

    public static void main(String[] args) {
        System.out.println(new Main279().numSquares(100));
    }
}
